#include <stdio.h>
#include <stdlib.h>

void sort(int* array, int nCnt)
{
    int* lpTmp = (int*)malloc(sizeof(int) * nCnt);
    if (!lpTmp) return;

    int nLeftA;         //  [
    int nRightA;        //  ]
    int nLeftB;         //  [
    int nRightB;        //  ]
    int nIndex;
    int nPerCnt = 1;    //  每组个数

    while (nPerCnt < nCnt)
    {
        for (int i = 0; i < nCnt; i += 2 * nPerCnt)
        {
            nLeftA = i;
            nRightA = i + nPerCnt - 1;
            nLeftB = i + nPerCnt;
            nRightB = i + 2 * nPerCnt - 1;
            nIndex = i;

            //
            //  若A组右区间不存在
            //

            if (nRightA >= nCnt - 1) break;

            //
            //  若B组右区间存在，但超出范围
            //

            if (nRightB >= nCnt)
                nRightB = nCnt - 1;

            //
            //  比较A组与B组
            //

            while (nLeftA <= nRightA && nLeftB <= nRightB)
            {
                if (array[nLeftA] < array[nLeftB])
                    lpTmp[nIndex++] = array[nLeftA++];
                else
                    lpTmp[nIndex++] = array[nLeftB++];
            }

            while (nLeftA <= nRightA)
                lpTmp[nIndex++] = array[nLeftA++];

            while (nLeftB <= nRightB)
                lpTmp[nIndex++] = array[nLeftB++];

            //
            //  拷贝至原数组
            //

            for (int k = i; k <= nRightB; k++)
                array[k] = lpTmp[k];
        }

        nPerCnt *= 2;
    }

    free(lpTmp);
}

int main()
{
    int array[9] = { 2,8,5,1,3,11,7,2,6 };

    sort(array, sizeof(array) / sizeof(int));

    for (unsigned int i = 0; i < (sizeof(array) / sizeof(int)); ++i)
        printf("%d ", array[i]);
    puts("");

    return 0;
}